package cn.ly.recursion.binarysearch;

import cn.ly.util.ArithmeticTool;

public class OrdArray {
	
	private long[] arr;
	private int size;
	
	public OrdArray(int len){
		arr = new long[10];
		this.size = 0;
	}
	
	public int getSize(){
		return size;
	}
	
	public int find(long searchKey){
		return recFind(searchKey,0,size-1);
	}
	
	//递归的二分查找方法
	private int recFind(long key,int lower,int upper){
		int cur = (lower + upper)/2;
		if(arr[cur] == key){
			return cur;
		}else if(lower > upper){
			//当移动查找范围时，lower和upper的数字不和逻辑时（lower不能大于upper），
			//说明在整个数组中也没有找到整个数
			return size;
		}else{
			if(arr[cur] < key){//key比但前值大，去大的范围继续查找
				return recFind(key,cur+1,upper);
			}else{//反之key比但前值小，去小的范围继续递归查找
				return recFind(key,lower,cur-1);
			}
		}
	}
	
	//由于默认数组是升序排列，所以寻找当数组中的某一个元素大于当前需要插入的元素，那么整个位置就是需要插入位置
	public void insert(long value){
		int j = 0;
		for(;j < size; j++){
			if(arr[j] > value){
				break;
			}
		}
		for(int k=size; k > j; k--){
			//这里的size是原有数组的实际长度，那么最后一个下标是，size-1，那么后面的一个的下标就是size，
			//所以把a[k](a[size]) = a[k-1]，这样向后移动一个位置，把需要插入的位置腾空出来
			arr[k] = arr[k-1];
		}
		arr[j] = value;
		size++;
	}
	
	public void display(){
		for(int i=0; i<size; i++){
			System.out.print("["+i+"]"+arr[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		OrdArray oarr = new OrdArray(10);
		for(int i=0; i < 9;i++){
			oarr.insert(ArithmeticTool.getIntRandom0to100());
		}
		oarr.insert(26);
		oarr.display();
		
		System.out.println(oarr.find(26));
		
	}

}
